package a14_Sort;

/**
 * @Author quan
 * @Description 直接选择排序：不稳定
 * @Date 2023/4/26 22:19
 */
public class selectSort {
    //Notes: i表示无序区间的第一个元素
    //min是无序区间的最小值，j是无序区间一直遍历，找到最小值min之后一定与无序区间的第一个值交换。
    //此时就能确保每次有序区间增加的新值一定是满足递增的。
    //当最后无序区间只剩下一个元素的时候，就可以提前结束循环了。
    /**
     * 核心思路：每次在无序区间汇总选择最小值与无序区间的第一个值交换，直到整个数组有序
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {1,56,23,4,12,9,6,8,17};
        selectionSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void selectionSort(int[] arr){
        //起始状态：有序区间[0,i)
        //无序区间：[i,n)
        int min = 0;
        //min索引指向的值一定是无序区间的最小值
        //i索引指向的值是无序区间的第一个值
        for (int i = 0; i < arr.length-1; i++) {
            min = i;
            for (int j = i; j < arr.length; j++) {
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            //此时min指向的值一定是无序区间的最小值，换到无序区间的最开始位置
            swap(arr,min,i);
        }
    }
    //交换函数
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}